package com.xcoder.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/hanota-lcci/
 */
public class 汉诺塔问题 {

    public static void main(String[] args) {
        List<Integer> A = new ArrayList<>();
//        A.add(3);
        A.add(2);
        A.add(1);
        A.add(0);
        List<Integer> B = new ArrayList<>();
        List<Integer> C = new ArrayList<>();
        hanota(A, B, C);
        for (Integer c : C) {
            System.out.print(c + " ");
        }
    }

    private static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        hanoi(A.size(), A, B, C);
    }

    private static void hanoi(int n, List<Integer> A, List<Integer> B, List<Integer> C) {
        if (n == 1) {
            C.add(A.get(A.size() - 1));
            A.remove(A.size() - 1);
        } else {
            // 把A上的n-1个借助C移到B上
            hanoi(n - 1, A, C, B);
            // 把A最后一个移到C上
            C.add(A.get(A.size() - 1));
            A.remove(A.size() - 1);
            // 把B借助A移到C上
            hanoi(n - 1, B, A, C);
        }
    }
}
